#include <iostream>
#include <string>

using namespace std;

struct Node {
    int key;
    int priority;
    int size;
    Node* left;
    Node* right;

    Node(int k = 0, int p = 0) {
        key = k;
        priority = p;
        size = 1;
        left = NULL;
        right = NULL;
    }

};

void updateSize(Node* t) {
    if(t == NULL) return;
    int lSize, rSize;
    lSize=(t->left == NULL)? 0 : t->left->size;
    rSize=(t->right == NULL)? 0 : t->right->size;
    t->size = lSize + rSize + 1;
}

Node* merge(Node* l, Node* r) {
    if (l == NULL) {
        return r;
    }
    if (r == NULL) {
        return l;
    }

    if (l->priority > r->priority) {
        l->right = merge(l->right, r);
        updateSize(l);  
        return l;
    } else {
        r->left = merge(l, r->left);
        updateSize(r); 
        return r;
    }
}

void split(Node* t, int key, Node** l, Node** r) {
    if (t == NULL) {
        *l = NULL;
        *r = NULL;
        return;
    }

    if (t->key < key) {
        *l = t;
        split(t->right, key, &((*l)->right), r);
        updateSize(*l); 
    } else {
        *r = t;
        split(t->left, key, l, &((*r)->left));
        updateSize(*r); 
    }
}

void insert (Node** t, Node* n) {
    if (*t == NULL) { *t = n; }
    else {
        if (n->priority > (*t)->priority) {
            split(*t, n->key, &(n->left), &(n->right));
            *t = n;
        } else {
            if (n->key < (*t)->key) insert(&((*t)->left), n);
            else insert(&((*t)->right), n);
        }
    }
    updateSize(*t); 
}

void remove(Node** t, int key) {
    if (*t == NULL) return;
    if ((*t)->key == key) {
        *t = merge((*t)->left, (*t)->right);
    } else {
        if (key < (*t)->key) remove(&((*t)->left), key);
        else remove(&((*t)->right), key);
    }
    updateSize(*t); 
}

void print(Node* t) {
    if (t == NULL) {
        return;
    }
    print(t->left);
    cout<<t->key<<" ";
    print(t->right);
}

int kthkey(Node* t, int k) {
    while (t != NULL) {
        int lSize=(t->left == NULL)? 0 : t->left->size;
        
        if (lSize == k) return t->key;
        if (lSize < k) {
            t = t->right;
            k -= lSize + 1;
        }
        if (lSize > k) {
            t = t->left;
        }
    }

    return NULL;
}

int main() {
    Node* treap = NULL;
    int a;
    
    string command;

    cout<<"Command list: [add key], [delete key], [print], [kthkey k], [exit]"<<endl;

    while (true) {
        cin>>command;
        int a;

        if (command == "add") {
            cin>>a;
            Node* tmp = new Node(a, rand());
            insert(&treap, tmp);
            continue;
        }

        if (command == "delete") {
            cin>>a;
            remove(&treap, a);
            continue;
        }

        if (command == "print") {
            print(treap);
            cout<<endl;
            continue;
        }

        if (command == "kthkey") {
            cin>>a;
            cout<<a<<"-th key: "<<kthkey(treap, a)<<endl;
            continue;
        }

        if (command == "exit") {
            return 0;
        }

        cout<<"Error: invalid command"<<endl;
    }
}